import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/29 9:32
 */
// 岛屿最大面积
    // https://leetcode.cn/problems/max-area-of-island/
    // BFS+DFS
    // DFS优化后就是淹没思路
public class Solution695 {
    int[][] dir = {{0,1}, {1, 0}, {0,-1}, {-1,0}};
    int count = 0;
    int res = 0;
    boolean[][] visited;
    public int maxAreaOfIsland(int[][] grid) {
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    bfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }

    // 广度遍历算法
    private void bfs(int[][] grid, int i, int j) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] {i, j});
        visited[i][j] = true;
        count++;
        while(!que.isEmpty()) {
            int[] poll = que.poll();
            int curX = poll[0];
            int curY = poll[1];

            for (int[] dirVec : dir) {
                int nextX = curX + dirVec[0];
                int nextY = curY + dirVec[1];
                if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;
                if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                    que.offer(new int[] {nextX, nextY});
                    visited[nextX][nextY] = true;
                    count++;
                }
            }
        }
    }
}
